package leetcode算法面试题.字符串;

import java.io.Flushable;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class 分割回文串 {
    //这个我想到之前的回溯的思想
    class Solution{
        List<List<String>> res = new ArrayList<>();
        Deque<String> deq = new LinkedList<>();
        public List<List<String>> partition(String s){
           backTracing(s,0);
           return res;
        }

        private void backTracing(String s, int startIndex) {
            ///这里的终止条件 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
            if (startIndex>=s.length()){
                res.add(new ArrayList<>(deq));
                return;
            }
            for (int i = startIndex; i < s.length(); i++) {
                //判断是否为回文串 是的话就加入
                if (isPalindrome(s,startIndex,i)){
                    //substring取的位置是starIndex到i(写的是到i+1，但是只取到它前一位)
                    String str = s.substring(startIndex, i + 1);
                    deq.addLast(str);
                }else {
                    //如果不满足回文串 就继续当前for的循环
                    continue;
                }
                //向下遍历
                backTracing(s,i+1);
                //回溯
                deq.removeLast();
            }
        }

        private boolean isPalindrome(String s, int startIndex, int end) {
            for (int j = startIndex,i=end; i>0 && j < s.length() ; j++,i--) {
                if (s.charAt(i)!=s.charAt(j)) return false;
            }
             return true;
        }
    }
}
